package com.fr.lintcode;

import java.util.ArrayList;
import java.util.Arrays;

import org.junit.Test;

/**
*作者：furong
*日期：2016年12月26日
*时间：下午9:10:32
*/
public class Q50 {
    /**
     * @param A: Given an integers array A
     * @return: A Long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
     */
    public ArrayList<Long> productExcludeItself(ArrayList<Integer> A) {
        if (A == null || A.size() <= 0) {
            return null;
        }
        int size = A.size();
        ArrayList<Long> rs = new ArrayList<>();
        // c[i] = a[0] * a[1] ...a[i];
        long c[] = new long[size];
        // d[i] = a[n] * a[n-1] ...a[i];
        long d[] = new long[size];
        c[0] = A.get(0);
        d[size - 1] = A.get(size - 1);
        for (int i = 1; i < size; i++) {
            c[i] = c[i - 1] * A.get(i);
        }
        for (int i = size - 2; i >= 0; i--) {
            d[i] = d[i + 1] * A.get(i);
        }
        for (int i = 0; i < size; i++) {
            long cc = i - 1 < 0 ? 1 : c[i - 1];
            long dd = i + 1 > size - 1 ? 1 : d[i + 1];
            rs.add(cc * dd);
        }
        return rs;
    }

    @Test
    public void testA() {
        ArrayList<Integer> A = new ArrayList<>(Arrays.asList(1, 2, 3));
        System.out.println(productExcludeItself(A));
    }
}
